1. Field of the Invention
The present invention relates to public key cryptography.
2. Discussion of Related Art
It is well known that data can be encrypted by utilising a pair of keys, one of which is public and one of which is private. The keys are mathematically related such that data encrypted by the public key may only be decrypted by the private key. In this way, the public key of a recipient may be made available so that data intended for that recipient may be encrypted with the public key and only decrypted by the recipients private key.
One well-known and accepted public key cryptosystem is that based upon discrete logarithms in finite groups. Different finite groups may be used, for example the multiplicative group Z*p of integers mod p where p is a prime; the multiplicative group of an arbitrary finite field e.g. GF2n or an elliptic curve group over a finite field.
The discrete log problem used in such cryptosystems is based on the difficulty of determining the value of an integer x from the value of xcex1x, even where xcex1 is known. More particularly, if xcex1 is an element of G (which is considered to be written multiplicatively) and xcex2 is a second element of G, then the discrete logarithm problem in G is that of determining whether there exists an integer x such that xcex2=xcex1x, and if so, of determining such a value x.
The Diffie-Hellman key exchange protocol is widely accepted and there are numerous examples of implementations of the Diffie-Hellman protocol in use around the world.
The Diffie-Hellman key agreement protocol is typically stated as follows using as an example the finite group Zpxc2x7:
Setup
The protocol requires a base xcex1 that generates a large number of elements of the selected group G and a pair of integers x,y that are retained confidential by respective correspondents A,B. Select a prime number p and let a be xcex1 generator of the multiplicative group Zpxc2x7, i.e. the group of integers modulo p.
The Protocol
1. Correspondent A generates a random integer x, computes xcex1x and sends this to correspondent B.
2. Correspondent B generates a random integer y, computes xcex1y and sends this to correspondent A.
3. A computes (xcex1y)x=xcex1xy.
4. B computes (xcex1x)y=xcex1xy.
A and B now share the common key xcex1xy which may be used as a secret key in a conventional cryptosystem. A similar protocol maybe used in a public key system, generally referred togas an El-Gamal protocol in which each correspondent has a secret key x and a public key xcex1x.
The security of these protocols seems to rest on the intractability of the discrete logarithm problem in the finite group G. It should also be noted that the protocol carries over to any finite group.
The applicants have now recognized that unless the generator xcex1 and the group G are selected carefully then the exchange of information may be weak and provide almost no security.
To explain the potential problem, consider the cryptosystem described above using the group Zpxc2x7. The modulus p is public information that defines the cryptosystem and can be expressed as t.Q+1 with txe2x89xa72 and t relatively small. This is always possible since p is odd for large primes (i.e. t could be 2).
Let S be a subgroup of Z*p of order t (i.e. it has t elements, each of which is element of Zpxc2x7) and let xcex3 be a base for S, i.e. each element of S can be expressed as an integral power of xcex3 and raising xcex3 to an integral power produces an element that is itself in the subgroup S. If xcex1 is a generator for Zpxc2x7, then we can take xcex3=xcex1Q without loss of generality.
If E is an active adversary in the key exchange protocol between two parties A and B then the attack proceeds as follows:
1. E intercepts the message xcex1x sent by A and replaces it by (xcex1x)Q=xcex3x and sends it on to entity B.
2. E intercepts the message xcex1y sent by B and replaces it by (xcex1y)Q=xcex3y and sends it on to entity B.
3. A computes (xcex3y)x=xcex3xy.
4. B computes (xcex3x)y=xcex3xy.
5. Although E does not know the key xcex3xy, E knows that the common key xcex3xy lies in the subgroup S of order t as xcex3 is a generator of S. By definition xcex3xy must produce an element in the subgroup S. Since S is of order t it has precisely t elements. If t is small enough then E can exhaustively check all possibilities and deduce the key.
Since E selects Q, t can always be taken to be 2 and so the threat is practical.
A similar attack may be mounted with cryptosystems using groups other than Z*p which will be vulnerable if the element selected as a base or generator generates a subgroup which itself has a small subgroup of order t.
It is therefore an object of the present invention to provide a method for checking if modification of messages has occurred or in the alternative some method to prevent the attack from being mounted.
In general terms, the present invention is based upon utilization of predefined characteristics of the order of the subgroup.
In one aspect, the base of the cryptosystem is chosen to be a generator of a subgroup of a relatively large prime order. Substitution of any other non-unit generator is of no advantage to an attacker since it does not produce an element in a smaller subgroup that can be exhaustively searched.
In another aspect, factors of the order of the group generated by the base are used to ensure that the key does not lie in or has not been modified to lie in a proper subgroup of relatively small order, i.e. one that may feasibly be exhaustively searched by an interloper.